约瑟夫环（单向循环链表） |
您所在的位置：网站首页 › 约瑟夫环 顺序表 › 约瑟夫环（单向循环链表） |
约瑟夫环（单向循环链表）
|
C语言「抄作业」系列之约瑟夫环（单向循环链表） 约瑟夫环（Josephus problem） 1世纪的犹太历史学家Josephus曾经记载有以下故事：罗马人占领乔塔帕特后，Josephus和40个犹太战友躲到一个洞中，大家选择死亡，并以抽签的方式决定死亡顺序。41个围成圆圈，依次报数。每报到3的人死亡，然后从下一人起重新报数，直至所有人死亡。当只剩下Josephus和另外一人时，Josephus说服了那个人，一起向罗马军队投降。 约瑟夫环，即根据以上故事，求得Josephus与另外一人最初的位次。另一人与Josephus与分别位于第16、第31的位置上。 /* 约瑟夫环（Josephus problem） */ /* 1世纪的犹太历史学家Josephus曾经记载有以下故事：*/ /* 罗马人占领乔塔帕特后，Josephus和40个犹太战友躲到一个洞中，大家选择死亡，并以抽签的方式决定死亡顺序。 */ /* 41个围成圆圈，依次报数。每报到3的人死亡，然后从下一人起重新报数，直至所有人死亡。 */ /* 当只剩下Josephus和另外一人时，Josephus说服了那个人，一起向罗马军队投降。 */ /* 约瑟夫环，即根据以上故事，求得Josephus与另外一人最初的位次。 */ /* 另一人与Josephus与分别位于第16、第31的位置上。 */ #include #include #include #define lElemType int /* 单向循环链表元素数据类型 */ #define LNODE_SIZE sizeof (struct lNode) /* 单向循环链表结点空间大小 */ #define status int /* 状态型变量 */ #define OVERFLOW -1 /* 内存溢出状态码 */ #define ERROR 0 /* 错误状态码 */ #define OK 1 /* 正确状态码 */ /* 单向循环链表数据结构 */ typedef struct lNode { lElemType data; struct lNode *next; } lNode, *cirLinkList; /********************************************************************************************/ void createJosephus (cirLinkList C, int n, int k); /* 创建约瑟夫环 */ void runJosephus (cirLinkList C, int n, int k); /* 执行约瑟夫环 */ /****************************** 带头结点的单向循环链表基本操作 ******************************/ void initList (cirLinkList *L); /* 初始化单向循环链表 */ void destroyList (cirLinkList *L); /* 销毁单向循环链表 */ void listTraverse (cirLinkList L, void (*vi)(lElemType)); /* 依次对单向循环链表的每个元素调用函数vi() */ /********************************************************************************************/ void vi (lElemType e); /* visit函数，定义为打印元素值 */ /********************************************************************************************/ /* 初始化单向循环链表 */ /* 操作结果：构造一个带头结点的空单向循环链表L */ void initList (cirLinkList *L) { *L = (cirLinkList) malloc (LNODE_SIZE); /* 生成头结点，并使L指向此头结点 */ if (!*L) /* 内存分配失败 */ exit (OVERFLOW); (*L)->next = *L; /* 指针域指向头结点 */ } /* 销毁单向循环链表 */ /* 初始条件：单向循环链表L已存在*/ /* 操作结果：销毁单向循环链表L */ void destroyList (cirLinkList *L) { cirLinkList p, q; p = (*L)->next; /* p指向L的首元结点 */ while (p != *L) { /* 尚未重新回到头结点 */ q = p->next; /* q指向p的后继 */ free (p); /* 释放p */ p = q; /* p向后移动 */ } free (*L); /* 释放L的头结点 */ *L = NULL; } /* 依次对单向循环链表的每个元素调用函数vi() */ /* 初始条件：单向循环链表L已存在 */ /* 操作结果：依次对L的每个数据元素调用函数vi() */ void listTraverse (cirLinkList L, void (*vi)(lElemType)) { cirLinkList p = L->next; /* p指向L的首元结点 */ if (p == L) /* 空表 */ puts ("The circular linked list is empty! "); while (p != L) { /* 尚未重新回到头结点 */ vi (p->data); /* 调用visit函数 */ p = p->next; } putchar ('\n'); } /* visit函数，访问数据元素 */ void vi (lElemType e) { printf ("%d ", e); /* 定义为打印元素值 */ } /* 创建约瑟夫环 */ /* n个人围成圆圈C */ void createJosephus (cirLinkList C, int n, int k) { cirLinkList p = C, s; int i; for (i=1; idata = i; /* 为第i个人编号 */ s->next = p->next; /* 新结点链接至原第i个结点 */ p->next = s; /* 原第i-1个结点链接至新结点 */ p = p->next; } } /* 执行约瑟夫环 */ /* n个人围成圆圈C，依次报数，报到k的人死亡 */ void runJosephus (cirLinkList C, int n, int k) { int i, j = n; cirLinkList p = C, q; createJosephus (C, n, k); /* 创建约瑟夫环 */ printf ("The initial circle:\n"); listTraverse (C, &vi); putchar ('\n'); printf("The order is:\n"); while (j>2) { /* 仅剩下Josephus与另外一人时结束 */ i = 0; /* 开始报数 */ while (inext; if (p!=C) /* 计数时跳过头结点 */ i++; } if (p->next == C) /* 第k-1个结点是尾结点 */ p = C; q = p->next; /* q指向p的后继，q即报到k之人 */ p->next = q->next; /* p的后继，跨过q，指向q的后继 */ printf("%d ", q->data); free (q); /* 释放q */ j--; /* 人数减一 */ } putchar ('\n'); putchar ('\n'); printf ("The other man and josephus in:\n"); listTraverse (C, &vi); } int main (void) { cirLinkList C; initList (&C); runJosephus (C, 41, 3); /* result: 16 31 */ //runJosephus (C, 8, 3); /* result: 4 7 */ destroyList (&C); getch (); /* 屏幕暂留 */ return 0 ; }运行结果  C语言抄作业系列，只有答案，没有讲解！ 计算机科学专业毕业多年的一个啥也没学会而转行做了产品经理的家伙，从当年的各种作业里搬运来的一些乱七八糟的东西。 |
【本文地址】
今日新闻 |
推荐新闻 |